Read the original article here.

---

The Arithmetic Logic Unit (ALU): The Heart of Computation

In the journey of building a computer from scratch, you will encounter fundamental building blocks. Among the most crucial is the Arithmetic Logic Unit (ALU). Think of the ALU as the computer's calculator – the specialized component responsible for performing all the basic arithmetic and logical operations that make a computer useful. Understanding the ALU is essential because it's where the actual data processing happens.

What is an ALU?

Arithmetic Logic Unit (ALU): A digital circuit that performs arithmetic operations (like addition, subtraction) and bitwise logic operations (like AND, OR, NOT) on integer binary numbers. It is a core component found in almost all computing circuits, including Central Processing Units (CPUs), Graphics Processing Units (GPUs), and Floating-Point Units (FPUs).

In simple terms, you give the ALU some data and tell it what to do with that data, and it gives you back the result. It's a purely combinational digital circuit, meaning its output at any given moment is determined solely by its current inputs. There's no internal memory or state that affects the calculation being done right now (though the system using the ALU will manage state).

While a simple ALU handles operations on integer binary numbers, more complex processors might have separate units like Floating-Point Units (FPUs) dedicated to handling numbers with decimal points (represented in a specific format called floating-point). However, the fundamental ALU is the workhorse for integer arithmetic and logical comparisons, which are the bedrock of almost all computation.

Building Block: Where Does the ALU Fit?

When you build a computer from scratch, the ALU is a central component connected to other parts of the system:

• Registers: These are small, fast storage locations where the CPU keeps data it's currently working with. The ALU often gets its input data from registers and sends its results to registers.
• Memory: While the ALU doesn't directly access main memory, data is moved between memory and registers, and then the ALU operates on the data in registers.
• Control Unit: This is the "brain" that orchestrates the entire process. It fetches instructions from memory, decodes them, and then tells the ALU which operation to perform and which data (from registers or other sources) to use.
• Status Register (or Flags): The ALU often provides information about the result of an operation (like if it was zero, negative, or caused an overflow). These status signals are stored in a dedicated register, used by the control unit for making decisions (like conditional jumps in your program).

The Signals of an ALU: Inputs and Outputs

To build or understand an ALU, you need to know its connection points – the electrical "wires" or "buses" that carry information in and out.

Data Inputs and Outputs

The most fundamental signals are the data buses:

• Operand A: A parallel bus carrying the first input binary number.
• Operand B: A parallel bus carrying the second input binary number.
• Result Y: A parallel bus carrying the binary result of the operation.

Operand: A piece of data that is an input to an operation.

These buses are "parallel" because they consist of multiple individual wires, one for each bit of the binary number. If you are building a computer with an 8-bit word size, each of these buses would have 8 wires. The width of these data buses determines the native word size the ALU can operate on directly.

Opcode Input

This input bus tells the ALU what operation to perform.

Opcode (Operation Code): A binary code that specifies the particular operation (like addition, subtraction, logical AND) the ALU should execute.

The opcode is essentially a numerical instruction for the ALU. The number of bits in the opcode bus determines how many different operations the ALU can support. A 3-bit opcode could specify up to 2^3 = 8 operations, a 4-bit opcode up to 16, and so on. This opcode signal is generated by the computer's control unit based on the instruction currently being executed.

Status Signals (Outputs and Inputs)

Status signals provide crucial information about the operation that just occurred or provide extra data to the operation.

Status Outputs (Flags)

These are typically individual wires (or "flags") that convey information about the result of the operation performed by the ALU. They are usually stored in a Status Register or Condition Code Register external to the ALU itself. Common status outputs include:

• Carry-out (C):
  • For addition: Indicates if the sum exceeded the maximum value representable by the ALU's word size, generating a carry bit out of the most significant bit position.
  • For subtraction: Often indicates a "borrow" was needed.
  • For shifts: Can hold the bit that was shifted out.
  • Use Case: Essential for performing arithmetic on numbers larger than the ALU's word size (multiple-precision arithmetic) and for some conditional branching.
• Zero (Z): Indicates that the result Y is all zeros.
  • Use Case: Used for checking if two numbers are equal (by subtracting them and checking the Zero flag) or if a value is zero. Critical for conditional branching like "jump if equal to zero".
• Negative (N): Indicates that the result of an arithmetic operation is negative. In two's complement representation, this is often simply a copy of the most significant bit (MSB) of the result.
  • Use Case: Used for checking the sign of a result, important for comparing numbers and conditional branching like "jump if negative".
• Overflow (V): Indicates that the result of a signed arithmetic operation has exceeded the range of values that can be represented in the ALU's word size using two's complement. This is different from carry-out, which is for unsigned overflow.
  • Use Case: Crucial for detecting errors in signed arithmetic calculations.
• Parity (P): Indicates whether the number of '1' bits in the result Y is even or odd.
  • Use Case: Less common in core computation, sometimes used for error detection or specific instructions.

Status Inputs

While ALUs often have multiple status outputs, the most common status input is:

• Carry-in (Cin): A single bit input that provides a carry (or borrow) from a previous operation.
  • Use Case: Absolutely vital for performing arithmetic operations on numbers larger than the ALU's native word size (multiple-precision arithmetic). It allows you to chain operations together.

How the ALU Works: Circuit Operation

An ALU is built from basic logic gates (AND, OR, NOT, XOR, etc.). For example, an adder circuit for one bit takes two input bits and a carry-in and produces a sum bit and a carry-out bit. To make an 8-bit adder, you would chain together 8 such 1-bit adder circuits, with the carry-out of one stage becoming the carry-in of the next. Similar logic gate arrangements build circuits for subtraction, AND, OR, and other operations.

The opcode input acts like a selector switch. Based on the value of the opcode, the ALU's internal circuitry directs the input operands A and B through the appropriate functional block (e.g., the adder circuit, the AND gate circuit, the shifter circuit). The output Y then receives the result from the selected operation.

Combinational Logic: A type of digital logic circuit whose output is a pure function of its current inputs. It has no memory of past inputs; the output changes instantaneously (subject to propagation delay) when inputs change. Propagation Delay: The time it takes for a change in the input of a logic circuit (or an entire ALU) to propagate through the gates and result in a stable, correct output.

Because the ALU is combinational, its output Y and status flags will change as soon as the inputs (A, B, Opcode, Cin) change. However, these changes don't happen instantly due to the physical nature of the electronic circuits; there's a small propagation delay.

In a computer built from scratch, external circuitry (specifically, the control unit and sequential logic like registers) manages the timing. The inputs to the ALU are held stable for a period, the control unit waits long enough for the propagation delay to pass, and then the result on the output Y and the status flags become valid and can be captured by a register or used for the next step. This timing is usually synchronized by a clock signal.

Example: ALU Operation Cycle (Simplified)

Imagine your simple CPU wants to perform ADD R1, R2 (add the contents of Register 1 and Register 2, store in Register 1).

1. Fetch & Decode: The control unit fetches the ADD R1, R2 instruction. It decodes this instruction.
2. Setup ALU Inputs:
   • The control unit configures multiplexers (selector circuits) to route the contents of Register 1 to the ALU's Operand A input.
   • It routes the contents of Register 2 to the ALU's Operand B input.
   • It sets the ALU's Opcode input to the code for "ADD".
   • For a simple addition (not adding a carry from a previous step), it sets the Carry-in input to 0.
3. ALU Computation: Stable signals representing the numbers from R1 and R2, the "ADD" opcode, and Carry-in=0 are applied to the ALU inputs. The ALU's internal adder circuit performs the binary addition.
4. Propagation Delay: The control unit waits for the result to propagate through the ALU circuitry.
5. Capture Result: Once the result is stable, the control unit signals Register 1 (or another designated destination register) to capture the value currently on the ALU's Result Y output.
6. Capture Status: Simultaneously, the control unit signals the Status Register to capture the current state of the ALU's status outputs (Carry-out, Zero, Negative, Overflow, etc.).
7. Next Cycle: The ALU inputs can now be changed for the next instruction.

This demonstrates how the combinational ALU is used within a sequential system (the CPU) orchestrated by a clock.

Common Functions Performed by an ALU

While the specifics vary, most general-purpose ALUs support a standard set of operations:

Arithmetic Operations

These operations treat the input operands as binary numbers (signed or unsigned) and perform mathematical calculations.

• Add: Calculates A + B. The sum appears at Y, and the carry-out signal indicates an unsigned overflow.
• Add with Carry: Calculates A + B + Carry-in. This is crucial for adding numbers larger than the ALU's word size.
• Subtract: Calculates A - B (or B - A, depending on design). The difference appears at Y. The carry-out often indicates a "borrow" (depending on implementation, it might be inverted relative to an adder's carry). Can also be used for comparison (A-B, then check flags).
• Subtract with Borrow: Calculates A - B - Borrow-in (where Borrow-in is usually the Carry-out from the previous, less significant subtraction). Essential for subtracting numbers larger than the ALU's word size.
• Two's Complement (Negate): Calculates 0 - A (or 0 - B). This effectively flips the bits of the operand and adds 1, resulting in the two's complement representation of the number (its negative equivalent in signed arithmetic).
• Increment: Calculates A + 1 (or B + 1). A simple optimization of the add operation.
• Decrement: Calculates A - 1 (or B - 1). A simple optimization of the subtract operation.

Bitwise Logical Operations

These operations treat the input operands as collections of independent bits and perform a logical operation on each corresponding pair of bits (bit 0 of A with bit 0 of B, bit 1 of A with bit 1 of B, etc.).

• AND: Performs the logical AND operation bit by bit on A and B. (e.g., 1 AND 1 = 1, 1 AND 0 = 0, 0 AND 1 = 0, 0 AND 0 = 0). Useful for masking bits (setting specific bits to 0).
• OR: Performs the logical OR operation bit by bit on A and B. (e.g., 1 OR 1 = 1, 1 OR 0 = 1, 0 OR 1 = 1, 0 OR 0 = 0). Useful for setting specific bits to 1.
• Exclusive-OR (XOR): Performs the logical XOR operation bit by bit on A and B. (e.g., 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0). Useful for flipping specific bits or for comparisons (if bits are the same, result is 0).
• Ones' Complement (NOT): Performs the logical NOT operation bit by bit on A (or B). This simply inverts every bit (0 becomes 1, 1 becomes 0).

Bit Shift Operations

These operations move the bits of an operand left or right. Simple ALUs might only shift by one position, while more advanced designs might include a Barrel Shifter capable of shifting by multiple positions in a single operation. The bit shifted out often appears on the Carry-out status line.

• Arithmetic Shift: Shifts the operand left or right. When shifting right, the most significant bit (sign bit) is replicated to preserve the sign of the number (assuming two's complement representation). When shifting left, zeros are typically shifted in from the right.
  • Use Case: Used for multiplying (left shift) or dividing (right shift) signed numbers by powers of 2.
• Logical Shift: Shifts the operand left or right. Zeros are always shifted into the vacated positions (either from the right for left shifts, or from the left for right shifts).
  • Use Case: Used for manipulating unsigned numbers or treating the data simply as a sequence of bits. Left logical shift by N is equivalent to multiplying by 2^N for unsigned numbers. Right logical shift by N is equivalent to dividing by 2^N for unsigned numbers.
• Rotate: Shifts the bits left or right, but the bit shifted out of one end is shifted into the other end, treating the word as a circular buffer. The Carry-out may still capture the bit that "wrapped around".
  • Use Case: Useful for specific bit manipulations and cryptography.
• Rotate Through Carry: Similar to rotate, but the Carry flag is included in the circular buffer. Shifting one way moves bits into the Carry flag and the old Carry flag into the word; shifting the other way moves bits out the other end into the Carry flag and the old Carry flag into the word.
  • Use Case: Allows for rotating bits across the boundary of the word size, useful in some cryptographic algorithms or for efficiently implementing wider rotations using a narrow ALU.

Other Operations

Some ALUs might include a simple "pass through" operation:

• Pass Through: Simply copies the value of operand A (or B) to the result Y without modification.
  • Use Case: Useful for quickly checking the status flags of a register's content (e.g., is this register zero? is it negative?) without performing any calculation, or simply moving data through the ALU datapath.

Putting the ALU to Work: Applications

The ALU is a core component in virtually every operation a computer performs.

Using Status Flags

As mentioned, the ALU's status outputs (flags) are critical. After an operation, the control unit typically saves these flags in the Status Register. Subsequent instructions, particularly conditional branches, check these flags to decide the next course of action.

For example, a JUMP IF ZERO instruction would check the Zero flag in the Status Register. If it's set (meaning the previous ALU operation resulted in zero), the control unit changes the program counter to jump to a different part of the code. If it's not set, execution continues sequentially.

Connecting Operands and Results

In a typical simple CPU architecture, the ALU doesn't magically get its inputs. Multiplexers are used to select the sources for the ALU's operands. These sources could be:

• Registers (often two different registers from a Register File)
• An Immediate Value (a constant number embedded directly within the instruction)
• Data just read from memory

The ALU's result Y is then routed via control signals to its destination, which could be:

• A register (back into the Register File)
• Memory (via other circuits)

This network of registers, multiplexers, the ALU, and connections for data movement is often called the Datapath.

Multiple-Precision Arithmetic

One practical application of the ALU's status flags (specifically Carry-in and Carry-out) is performing arithmetic on numbers larger than the ALU's native word size.

Multiple-Precision Arithmetic: Algorithms that perform arithmetic operations on numbers that are larger than the word size of the processor's ALU by breaking the large number into smaller "fragments" that fit the ALU, and processing these fragments sequentially.

Imagine you have an 8-bit ALU but need to add two 16-bit numbers. You can treat each 16-bit number as two 8-bit fragments: a "least significant" (LS) byte and a "most significant" (MS) byte.

1. Add LS Bytes: Add the LS byte of the first number and the LS byte of the second number using the 8-bit ALU. Set the Carry-in for this first operation to 0. Store the 8-bit result (the LS byte of the final sum). The ALU will produce a Carry-out if there was a carry from bit 7 to bit 8 (which is outside the 8-bit word).
2. Store Carry: The control unit saves the Carry-out from the LS byte addition in the Status Register.
3. Add MS Bytes: Add the MS byte of the first number and the MS byte of the second number using the 8-bit ALU. This time, set the Carry-in input to the Carry-out value saved from the previous step. Store the 8-bit result (the MS byte of the final sum). The Carry-out from this step indicates if the total 16-bit sum caused an overflow.

By performing two 8-bit additions and managing the carry flag, you've successfully added two 16-bit numbers using an 8-bit ALU. This principle extends to any size number, showing how a basic ALU can be leveraged by software or microcode for more complex tasks. Similar techniques apply to subtraction and shifts using the borrow/carry flags.

Implementation: How is an ALU Built?

At the lowest level, an ALU is constructed from fundamental logic gates. For example, an adder circuit is built from XOR and AND gates. A subtractor can be built using an adder and negating one operand using the two's complement logic (which itself is NOT gates and an adder). Logical operations are simple parallel arrangements of AND, OR, XOR, and NOT gates, one for each bit. Multiplexers (selector circuits) are built from AND and OR gates and are used to select which function's output becomes the final ALU result Y based on the opcode.

In modern computing, ALUs are often designed using Hardware Description Languages (HDLs) like VHDL or Verilog, which describe the logic circuits. This description is then synthesized into a physical layout of transistors on an integrated circuit (chip).

Historically, before large-scale integration, ALUs were built using many individual logic gate chips or, earlier, even individual transistors or relays. The challenge was building wider ALUs (e.g., 16-bit, 32-bit). Techniques like Carry Lookahead were developed to speed up the carry propagation in adders, as waiting for the carry to ripple through each bit could be slow for wide ALUs. Some early designs used "bit-slice" ALUs, which were chips that implemented a narrow ALU (like 4 bits) but included special inputs/outputs for carry and status that allowed them to be chained together to create wider ALUs (e.g., using four 4-bit bit-slice ALUs to build a 16-bit ALU). The 74181 TTL chip was a famous example of an early integrated circuit ALU (a 4-bit slice).

As transistors became smaller (following Moore's Law), it became possible to integrate full-width ALUs onto a single chip, leading to the microprocessors we know today. Modern ALUs are highly optimized and can perform operations extremely quickly.

History Snippet

The concept of the ALU is credited to mathematician John von Neumann, who described it in 1945 as part of the design for the EDVAC computer. Early ALUs were often serial (processing one bit at a time) due to the cost and size of circuitry. The move to parallel ALUs (processing multiple bits simultaneously) significantly increased computer speed.

Conclusion

The Arithmetic Logic Unit is a cornerstone of digital computation. By understanding its inputs, outputs, core functions, and how it interacts with other components like registers and the control unit, you gain deep insight into how a computer performs calculations and makes decisions. When building a computer from scratch, the ALU (or a collection of logic circuits acting as one) will be the central unit you design or integrate to bring your machine to life and enable it to perform useful work.